import java.util.ArrayList;
import java.util.HashMap;
import java.util.HashSet;
import java.util.List;
/*
要求：频率栈优先弹出存储数量最多的，相等频率元素，按照后入先出原则弹出
策略：记录每个元素的存储频次和不同频次的所有元素，利用动态数组模拟堆栈，从后向前遍历模拟后入先出，遍历到最大频次元素弹出并更新 FreqStack
 */
public class SeqStack {
}
class FreqStack {
    HashMap<Integer,Integer> valMap;
    HashMap<Integer, HashSet<Integer>> seqMap;
    int maxSeq;
    List<Integer> list;

    public FreqStack() {
        this.valMap = new HashMap();
        this.seqMap = new HashMap();
        this.maxSeq = 0;
        this.list = new ArrayList();
    }

    public void push(int val) {
        if(valMap.containsKey(val)){
            int preSeq = valMap.get(val);
            valMap.put(val,preSeq+1);
            HashSet<Integer> hashSet = seqMap.getOrDefault(preSeq,new HashSet<>());
            hashSet.remove(val);
            if(hashSet.size()!=0)
                seqMap.put(preSeq,hashSet);
            else
                seqMap.remove(preSeq);
            HashSet<Integer> nextHashSet = seqMap.getOrDefault(preSeq+1,new HashSet<>());
            nextHashSet.add(val);
            seqMap.put(preSeq+1,nextHashSet);
        }else{
            valMap.put(val,1);
            HashSet<Integer> hashSet = seqMap.getOrDefault(1,new HashSet());
            hashSet.add(val);
            seqMap.put(1,hashSet);
        }
        this.maxSeq = Math.max(maxSeq,valMap.get(val));
        this.list.add(val);
    }

    public int pop() {
        if(maxSeq<1)return -1;
        int num = 0;
        HashSet<Integer> hashSet = seqMap.get(this.maxSeq);
        for(int i=this.list.size()-1;i>=0;i--){
            if(hashSet.contains(this.list.get(i))){
                num = this.list.get(i);
                this.list.remove(i);
                if(valMap.get(num)==1){
                    valMap.remove(num);
                }else{
                    valMap.put(num,valMap.get(num)-1);
                }
                if(hashSet.size()==1){
                    seqMap.remove(this.maxSeq);
                    if(this.maxSeq!=1){
                        HashSet<Integer> newSet = seqMap.getOrDefault(this.maxSeq-1,new HashSet<>());
                        newSet.add(num);
                        seqMap.put(this.maxSeq-1,newSet);
                    }
                    this.maxSeq-=1;
                }
                else{
                    hashSet.remove(num);
                    seqMap.put(this.maxSeq,hashSet);
                    if(this.maxSeq!=1){
                        HashSet<Integer> newSet = seqMap.getOrDefault(this.maxSeq-1,new HashSet<>());
                        newSet.add(num);
                        seqMap.put(this.maxSeq-1,newSet);
                    }
                }
                break;
            }
        }
        return num;
    }
}
